Addition is by far the most frequently occurring operation in datapath logic of microprocessors. Implementing an addition operation in hardware can be challenging when there is signal multiplicity, i.e., when the same input signal occurs more than once in the input operands of the addition operation. Techniques for removing redundancy on a gate-level netlist has been proposed, for example, in Brand, “Redundancy and Don't Cares in Logic Synthesis,” IEEE Transactions on Computers, vol. C-32, issue 10, pgs. 947-952 (October 1983) (hereinafter “Brand”), and in Cheng et al., “Multi-level logic optimization by redundancy addition and removal,” Proceedings of the 4th European Conference on Design Automation 1993 with the European Event in ASIC design, pgs. 373-377 (February 1993). With these techniques the adder is expanded to a gate-level netlist followed by the application of redundancy removal techniques to eliminate signal redundancies, e.g., by deleting redundant connections. However, this approach has high runtime and generates a solution that can have tradeoffs in terms of power-delay.
Tree adders are probably the most popular structures, especially for implementing multi-operand adder in a multiplier. See, for example, Wallace, “A Suggestion for a Fast Multiplier,” IEEE Transactions on Electronic Computer, vol. EC-13, issue 1, pgs. 14-17 (February 1964), and Dadda, “Some Schemes for Parallel Multipliers,” Alta Frequenza 34: pgs. 3490-356 (1965). However, algorithmic tree adders do not have any mention of optimization for signal multiplicity in the input operands.
Therefore, improved techniques for addressing signal multiplicity in the input operands while implementing an addition operation in hardware would be desirable.